package com.leetcode.partition8;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/8/24 9:45
 */
public class LC714买卖股票的最佳时机含手续费 {

    public static int maxProfit(int[] prices, int fee) {
        return greedy(prices, fee);
    }

    public static void main(String[] args) {
        int[] prices = {1, 3, 2, 8, 4, 9};
        int fee = 2;
        System.out.println(maxProfit(prices, fee));
    }

    private static int dynamicProgramming(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];      //第一天买入的情况
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);        //i天持有股票的情况
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);  //i天不持有股票的情况
        }
        for (int i = 0; i < prices.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[prices.length - 1][1];
    }

    private static int greedy(int[] prices, int fee) {
        int answer = 0, minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            //情况2：前一天是收获利润区间的最后一天（相当于真正的卖出），今天需要重新记录最小价格
            minPrice = Math.min(minPrice, prices[i]);       //始终记录最低价格，在最低价格买入

            //情况3：不做操作，保持原有状态，此时买则不便宜，卖则亏本
            if (prices[i] >= minPrice && minPrice >= prices[i] - fee) continue;
            if (prices[i] > minPrice + fee) {
                answer += prices[i] - minPrice - fee;
                //情况1：收获利润的这一天不是收获利润区间的最后一天（不是真正的卖出，相当于持有股票），后面需要继续收获利润
                minPrice = prices[i] - fee;
            }
        }
        return answer;
    }
}
